package random;

/**
 * 二进制求和
 *
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * 输入为 非空 字符串且只包含数字 1 和 0。
 */

public class L67 {

    public static void main(String[] args) {

        String a = "11";
        String b = "1";
        String s = addBinary1(a, b);
        System.out.println(s);
    }


    /*
    官方答案
    一、使用自带的方法，先变成十进制相加再转为二进制（超时的）
    如果字符串超过 33 位，不能转化为 Integer
    如果字符串超过 65 位，不能转化为 Long
    如果字符串超过 500000001 位，不能转化为 BigInteger
     */
    public static String addBinary1(String a, String b) {

        return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );

    }

    /*
    二、模拟
    我们可以借鉴[列竖式]的方法，末尾对齐，逐位相加。在二进制的计算中[逢二进一]
    具体的，我们可以取 n=max{∣a∣,∣b∣} ，循环n次，从最低位开始遍历，我们使用一个变量 carry 表示上一个
    位置的进位，初始值为0。记当前位置对其的两个位 ai 和 bi ，则每一位的答案为 (carry+ai+bi)mod2

     */
    public static String addBinary2(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
//
//        作者：LeetCode-Solution
//        链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    }
}
